// https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/

// 算法思路总结：
// 1. 两次二分查找分别定位目标值的起始和结束位置
// 2. 第一次查找第一个等于目标值的位置
// 3. 第二次查找最后一个等于目标值的位置
// 4. 使用统一的左开右开区间二分模板
// 5. 时间复杂度：O(log n)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    vector<int> searchRange(vector<int>& nums, int target) 
    {
        int n = nums.size();
        vector<int> ret;

        int l = -1, r = n;
        while (l + 1 != r)
        {
            int mid = (l + r) >> 1;
            if (nums[mid] < target)
            {
                l = mid;
            }
            else
            {
                r = mid;
            }
        }
        
        if (r == n || nums[r] != target)
        {
            return {-1, -1};
        }
        ret.push_back(r);

        r = n;
        while (l + 1 != r)
        {
            int mid = (l + r) >> 1;
            if (nums[mid] <= target)
            {
                l = mid;
            }
            else
            {
                r = mid;
            }
        }
        ret.push_back(l);

        return ret;
    }
};

int main()
{
    vector<int> nums1 = {5,7,7,8,8,10}, nums2 = {5,7,7,8,8,10};
    int target1 = 8, target2 = 6;

    Solution sol;

    vector<int> v1 = sol.searchRange(nums1, target1);
    vector<int> v2 = sol.searchRange(nums2, target2);

    for (const int& num : v1)
        cout << num << " ";
    cout << endl;

    for (const int& num : v2)
        cout << num << " ";
    cout << endl;   

    return 0;
}